package com.ruijixiang.leetcode.hot100;

public class leetcode2060 {
    /**
     * 方法一：采用头插法 (最简单)
     * 方法二：迭代
     * 方法三：递归
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head){
        // 方法一：头插法
//        ListNode preHead=new ListNode(0);
//        while(head!=null){
//            ListNode tmpNode=head;
//            head=head.next;
//            tmpNode.next=preHead.next;
//            preHead.next=tmpNode;
//        }
//        return preHead.next;
        // 方法二：迭代
//        ListNode prev=null;
//        ListNode curr=head;
//        while(curr!=null){
//            ListNode next=curr.next;
//            curr.next=prev;
//            prev=curr;
//            curr=next;
//        }
//        return prev;

        // 方法三：递归
        if(head==null || head.next==null){
            return head;
        }
        ListNode newHead=reverseList(head.next);
        head.next.next=head;
        head.next=null;
        return newHead;
    }
}
